import cplex
import itertools as it
import MYGRAPH_CLASS as mgc

class Ilp:
    def __init__(self, MyGraph, Max_Path_Length):
        self.OurGraph = MyGraph
        self.Prob = cplex.Cplex()
        self.Path_List = self.Return_All_Perms_Up_To_Length(self.OurGraph.DC_List, Max_Path_Length)
        self.Lat_Consts = []
        self.Cost_Consts = []
        self.Temp_Cost_List = []
        self.Upper_Bound_List = []
        self.Type_List = []
        self.User_Num = self.OurGraph.NUM_USERS
        self.DC_Num = self.OurGraph.NUM_DCS
        self.Path_Num = len(self.Path_List)
        self.Group_Num = self.OurGraph.NUM_GROUPS

    ###################################################################################
    def Set_Objective(self):
        #First, we need to build a Cost_Constraint and a Latency_Constraint list 
        #to be used as we build the objective and constraints.
        for User in self.OurGraph.User_List:
            for DC in self.OurGraph.DC_List:
                for Path in self.Path_List:
                    self.Lat_Consts.append(self.OurGraph.Calc_Latency_Of_DC_List(Path, User, DC))
                    self.Cost_Consts.append(self.OurGraph.Calc_Cost_Of_DC_List(Path, User, DC))
        
        # Now we'll start calculating the coefficients for the latency constrants 
        # and the cost constraints, which will be used in the objective function
        for U in range(len(self.OurGraph.User_List)):
            for D in range(len(self.OurGraph.DC_List)):
                for P in range(len(self.Path_List)):
                    self.Temp_Cost_List.append(self.Cost_Consts\
                        [U * self.DC_Num * self.Path_Num + D * self.Path_Num + P])
                    self.Upper_Bound_List.append(1)
                    self.Type_List.append("I")

        # Adds coefficients to the cost list for the group host variables
        #Since the VM# variables replaced these in the objective function, the 
        #coefficient is set to zero
        for G_Num in range(self.OurGraph.NUM_GROUPS):
            for DC in self.OurGraph.DC_List:
                self.Temp_Cost_List.append(0)
                self.Upper_Bound_List.append(1)
                self.Type_List.append("I")
        
        # Adds coefficients to the cost list reflecting forwarding costs of the DCs
        for DC in self.OurGraph.DC_List:
            self.Temp_Cost_List.append(self.OurGraph.node[DC]['cost'])
            self.Upper_Bound_List.append(cplex.infinity)
            self.Type_List.append("I")
            
        #This last chunk adds the variables that keep track of how many VM's are needed
        #to host at each DataCenter:
        for DC in self.OurGraph.DC_List:
            self.Temp_Cost_List.append(self.OurGraph.node[DC]['cost'])
            self.Upper_Bound_List.append(cplex.infinity)
            self.Type_List.append("I")
        
        # So now our list of variables looks like [Path_Vars, Group_Host_Vars, Forwarding_Vars]
        # Element quantities are [Path_Num*DC_NUM*USER_NUM + Group_Num*DC_Num + DC_Num]
        
        self.Prob.objective.set_sense(self.Prob.objective.sense.minimize)
        self.Prob.variables.add(obj=self.Temp_Cost_List, ub=self.Upper_Bound_List, types=self.Type_List)
        
    ###################################################################################
    def Add_Latency_Constraints(self):
        #Now we need to start adding the constraints.  We'll start with the latency constraints
        for U in range(self.User_Num):
            for D in range(self.DC_Num):
                for P in range(self.Path_Num):
                    #row = [[Pos_List, Zero_List]]
                    row = [[[U*self.DC_Num*self.Path_Num + D*self.Path_Num + P],\
                             [self.Lat_Consts[U*self.DC_Num*self.Path_Num + D*self.Path_Num + P]]]]
                    self.Prob.linear_constraints.add(lin_expr = row, senses = "L", rhs = [self.OurGraph.MAX_LATENCY])
            
        #Now We'll add the forwarding constraints, that is constrain our variables
        #such that the number of rented VS is minimized:
        #for Group_Num in range(OurGraph.NUM_GROUPS):
        for DC in self.OurGraph.DC_List:
            Col_List = []
            Coefficient_List = []
            Col_List.append(self.User_Num*self.DC_Num*self.Path_Num + \
                    self.OurGraph.NUM_GROUPS*self.DC_Num + self.OurGraph.DC_List.index(DC))
            Coefficient_List.append(1)
            for P in range(len(self.Path_List)):
                if DC in self.Path_List[P]:
                    for U in range(len(self.OurGraph.User_List)):
                        for D in range(len(self.OurGraph.DC_List)):
                            Col_List.append(U*self.DC_Num*self.Path_Num + D*self.Path_Num + P)
                            Coefficient_List.append(-1.0/self.OurGraph.PATHS_PER_SERVER)
            row = [[Col_List, Coefficient_List]]
            self.Prob.linear_constraints.add(lin_expr = row, senses = "L", rhs = [1])
            self.Prob.linear_constraints.add(lin_expr = row, senses = "G", rhs = [0])
        
        #Here is the constraint that each user has exactly one path:
        for U in range(len(self.OurGraph.User_List)):
            Col_List = []
            Coefficient_List = []
            for D in range(len(self.OurGraph.DC_List)):
                for P in range(len(self.Path_List)):
                    Col_List.append(U*self.DC_Num*self.Path_Num + D*self.Path_Num + P)
                    Coefficient_List.append(1)
            row = [[Col_List, Coefficient_List]]
            self.Prob.linear_constraints.add(lin_expr = row, senses = "E", rhs = [1])
    
        #Here is the constraint that every group needs a host, and only one:
        for G in range(self.OurGraph.NUM_GROUPS):
            Col_List = []
            Coefficient_List = []
            for D in range(len(self.OurGraph.DC_List)):
                Col_List.append(self.Path_Num*self.DC_Num*self.User_Num + G*self.DC_Num + D)
                Coefficient_List.append(1)
            row = [[Col_List, Coefficient_List]]
            self.Prob.linear_constraints.add(lin_expr = row, senses = "E", rhs = [1])
    
        #connect host variables to path variables (make host variable times Users in group
        #less than or equal to sum of paths from group members to DC): U-D-P
        for G in range(self.OurGraph.NUM_GROUPS):
            for D in range(self.OurGraph.NUM_DCS):
                Col_List = []
                Coefficient_List = []
                Num_In_Group = 0
                for U in range(self.OurGraph.NUM_USERS):
                    if self.OurGraph.User_List[U].Group is G:
                        Num_In_Group = Num_In_Group + 1
                        for P in range(len(self.Path_List)):
                            Col_List.append(U*self.DC_Num*self.Path_Num + D*self.Path_Num + P)
                            Coefficient_List.append(1)
                Col_List.append(self.User_Num*self.DC_Num*self.Path_Num + G*self.DC_Num + D)
                Coefficient_List.append(0 - Num_In_Group)
                row = [[Col_List, Coefficient_List]]
                self.Prob.linear_constraints.add(lin_expr = row, senses = "E", rhs = [0])
                
        #This constrains the VM# variables to be greater than or equal to the number
        #of VMS that will be required to host.
        for D in range(self.OurGraph.NUM_DCS):
            Col_List = []
            Coefficient_List = []
            Col_List.append(self.User_Num*self.DC_Num*self.Path_Num + self.Group_Num*self.DC_Num \
                + self.DC_Num + D)
            Coefficient_List.append(1)
            for G in range(self.OurGraph.NUM_GROUPS):
                Col_List.append(self.User_Num*self.DC_Num*self.Path_Num + G*self.DC_Num + D)
                Coefficient_List.append((-1.0/self.OurGraph.USERS_PER_VM)*self.OurGraph.Group_Sizes[G])
            row = [[Col_List, Coefficient_List]]
            self.Prob.linear_constraints.add(lin_expr = row, senses = "G", rhs = [0])
                
        
    ###################################################################################
    def Solve_Problem(self):
        self.Prob.solve()
        
    ###################################################################################
    def Print_Solution(self):
        Soln = self.Prob.solution.get_values()
        Max_Path_Length = 0
        for S in range(len(Soln)):
            if Soln[S] != 0.0:
                if S < self.User_Num*self.DC_Num*self.Path_Num:
                    print(str(self.OurGraph.DC_List[int(S/self.Path_Num)%self.DC_Num])\
                           + ", " + str(self.Path_List[S%self.Path_Num]))
                    if len(self.Path_List[S%self.Path_Num]) > Max_Path_Length:
                        Max_Path_Length = len(self.Path_List[S%self.Path_Num])
                elif S < self.User_Num*self.DC_Num*self.Path_Num + self.Group_Num*self.DC_Num:
                    print("Group: " + str(int(S - self.User_Num*self.DC_Num*self.Path_Num)/self.DC_Num) + ", DC: "\
                          + str(self.OurGraph.DC_List[int(S - self.User_Num*self.DC_Num*self.Path_Num)%self.DC_Num]))
                elif S < self.User_Num*self.DC_Num*self.Path_Num + self.Group_Num*self.DC_Num + self.DC_Num:
                    print("Forwarding DCs: " + \
                          str(self.OurGraph.DC_List[(S - self.User_Num*self.DC_Num*self.Path_Num + self.Group_Num*self.DC_Num)%self.DC_Num]))
                else:
                    print("Host " + str(self.OurGraph.DC_List[(S - self.User_Num*self.DC_Num*self.Path_Num + self.Group_Num*self.DC_Num + self.DC_Num)%self.DC_Num]) + \
                          " required " + str(Soln[S]) + " VM's to host.")

        print(self.Prob.solution.get_objective_value())
        return Max_Path_Length

    ###################################################################################
    def Get_Soln(self):
        return(self.Prob.solution.get_objective_value())
    
    ###################################################################################
    #Make sure you've already solved the ILP before you call this
    def Print_Path_Lats(self):
        Soln = self.Prob.solution.get_values()
        for i in range(self.DC_Num*self.User_Num*self.Path_Num):
            if Soln[i] != 0.0:
                print self.Lat_Consts[i]
        
    ###################################################################################
    def Return_All_Perms_Up_To_Length(self, MyList, length):
        Return_List = []
        for i in range(0, length + 1):
            for Combo in it.combinations(MyList, i):
                for Perm in it.permutations(Combo):
                    Return_List.append(list(Perm))
        return Return_List
        
    ####################################################################################
    def Print_DC_List(self):
        '''
        for dc in self.OurGraph.DC_List:
            print("(" + str(dc.x) + ", " + str(dc.y) + ")")
        
        print()
        
        for us in self.OurGraph.User_List:
            print("(" + str(us.x) + ", " + str(us.y) + ")")
        '''
        
        for dc in self.OurGraph.DC_List:
            print(dc)
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
